/*
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.
*/

class Solution {
public:
    bool _search(int A[], int low, int high, int target) {
        if (high < low) return false;
        int mid = (low + high) >> 1;
        if (A[mid] == target) return true;
        else if (A[low] < A[mid]) {
            // left is ordered
            if (A[low] <= target && target < A[mid]) {
                return _search(A, low, mid-1, target);
            } else {
                return _search(A, mid+1, high, target);
            }
        } else if (A[low] > A[mid]) {
            // right is ordered
            if (A[mid] < target && target <= A[high]) {
                return _search(A, mid+1, high, target);
            } else {
                return _search(A, low, mid-1, target);
            }
        } else { // A[low] == A[mid]
            if (A[mid] != A[high]) {
                // left must be all dupliates, search right
                return _search(A, mid+1, high, target);
            } else {
                // have to search both sides
                return (_search(A, low, mid-1, target) ||
                        _search(A, mid+1, high, target));
            }
        }
    }
    bool search(int A[], int n, int target) {
        return _search(A, 0, n-1, target);
    }
};
